//
// Created by liushuai on 2020/4/29.
//
#include "kmp.h"

int* Next(std::string &pattern) {
    int pattern_length = static_cast<int>(pattern.length());
    int* n = new int[pattern_length+1];
    n[0] = -1;
    int j = 0, k = -1;
    while (j < pattern_length) {
        if (k == -1 || pattern[j] == pattern[k]) {
            ++j;
            ++k;
            n[j] = k;
        } else
            k = n[k];
    }
    return n;
}

int kmp(std::string target, std::string pattern) {
    int i = 0, k = 0;
    int target_length = target.length();
    int pattern_length = pattern.length();
    int* n = Next(pattern);
    // 无法比较-1和pattern_length长度
    while (i < target_length && k < pattern_length) {
        if (k == -1 || target[i] == pattern[k]) {
            i++;
            k++;
        } else
            k = n[k];
    }
    delete [] n;
    if (k == pattern.length())
        return i - k;
    else
        return -1;
}